home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / espresso.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  3.4 KB  |  131 lines  |  [TEXT/R*ch]
  1. /*
  2.  *  Module: espresso.c
  3.  *  Purpose: The main espresso algorithm
  4.  *
  5.  *  Returns a minimized version of the ON-set of a function
  6.  *
  7.  *  The following global variables affect the operation of Espresso:
  8.  *
  9.  *  MISCELLANEOUS:
  10.  *      trace
  11.  *          print trace information as the minimization progresses
  12.  *
  13.  *      remove_essential
  14.  *          remove essential primes
  15.  *
  16.  *      single_expand
  17.  *          if true, stop after first expand/irredundant
  18.  *
  19.  *  LAST_GASP or SUPER_GASP strategy:
  20.  *      use_super_gasp
  21.  *          uses the super_gasp strategy rather than last_gasp
  22.  *
  23.  *  SETUP strategy:
  24.  *      recompute_onset
  25.  *          recompute onset using the complement before starting
  26.  *
  27.  *      unwrap_onset
  28.  *          unwrap the function output part before first expand
  29.  *
  30.  *  MAKE_SPARSE strategy:
  31.  *      force_irredundant
  32.  *          iterates make_sparse to force a minimal solution (used
  33.  *          indirectly by make_sparse)
  34.  *
  35.  *      skip_make_sparse
  36.  *          skip the make_sparse step (used by opo only)
  37.  */
  38.  
  39. #include "espresso.h"
  40.  
  41. pcover espresso(F, D1, R)
  42. pcover F, D1, R;
  43. {
  44.     pcover E, D, Fsave;
  45.     pset last, p;
  46.     cost_t cost, best_cost;
  47.  
  48. begin:
  49.     Fsave = sf_save(F);        /* save original function */
  50.     D = sf_save(D1);        /* make a scratch copy of D */
  51.  
  52.     /* Setup has always been a problem */
  53.     if (recompute_onset) {
  54.     EXEC(E = simplify(cube1list(F)),     "SIMPLIFY   ", E);
  55.     free_cover(F);
  56.     F = E;
  57.     }
  58.     cover_cost(F, &cost);
  59.     if (unwrap_onset && (cube.part_size[cube.num_vars - 1] > 1)
  60.       && (cost.out != cost.cubes*cube.part_size[cube.num_vars-1])
  61.       && (cost.out < 5000))
  62.     EXEC(F = sf_contain(unravel(F, cube.num_vars - 1)), "SETUP      ", F);
  63.  
  64.     /* Initial expand and irredundant */
  65.     foreach_set(F, last, p) {
  66.     RESET(p, PRIME);
  67.     }
  68.     EXECUTE(F = expand(F, R, FALSE), EXPAND_TIME, F, cost);
  69.     EXECUTE(F = irredundant(F, D), IRRED_TIME, F, cost);
  70.  
  71.     if (! single_expand) {
  72.     if (remove_essential) {
  73.         EXECUTE(E = essential(&F, &D), ESSEN_TIME, E, cost);
  74.     } else {
  75.         E = new_cover(0);
  76.     }
  77.  
  78.     cover_cost(F, &cost);
  79.     do {
  80.  
  81.         /* Repeat inner loop until solution becomes "stable" */
  82.         do {
  83.         copy_cost(&cost, &best_cost);
  84.         EXECUTE(F = reduce(F, D), REDUCE_TIME, F, cost);
  85.         EXECUTE(F = expand(F, R, FALSE), EXPAND_TIME, F, cost);
  86.         EXECUTE(F = irredundant(F, D), IRRED_TIME, F, cost);
  87.         } while (cost.cubes < best_cost.cubes);
  88.  
  89.         /* Perturb solution to see if we can continue to iterate */
  90.         copy_cost(&cost, &best_cost);
  91.         if (use_super_gasp) {
  92.         F = super_gasp(F, D, R, &cost);
  93.         if (cost.cubes >= best_cost.cubes)
  94.             break;
  95.         } else {
  96.         F = last_gasp(F, D, R, &cost);
  97.         }
  98.  
  99.     } while (cost.cubes < best_cost.cubes ||
  100.         (cost.cubes == best_cost.cubes && cost.total < best_cost.total));
  101.  
  102.     /* Append the essential cubes to F */
  103.     F = sf_append(F, E);                /* disposes of E */
  104.     if (trace) size_stamp(F, "ADJUST     ");
  105.     }
  106.  
  107.     /* Free the D which we used */
  108.     free_cover(D);
  109.  
  110.     /* Attempt to make the PLA matrix sparse */
  111.     if (! skip_make_sparse) {
  112.     F = make_sparse(F, D1, R);
  113.     }
  114.  
  115.     /*
  116.      *  Check to make sure function is actually smaller !!
  117.      *  This can only happen because of the initial unravel.  If we fail,
  118.      *  then run the whole thing again without the unravel.
  119.      */
  120.     if (Fsave->count < F->count) {
  121.     free_cover(F);
  122.     F = Fsave;
  123.     unwrap_onset = FALSE;
  124.     goto begin;
  125.     } else {
  126.     free_cover(Fsave);
  127.     }
  128.  
  129.     return F;
  130. }
  131.